package prefixTree;

import javax.lang.model.element.NestingKind;

public class PrefixTree {
	public static int MAXN=15001;
	
	public static int[][] tree=new int[MAXN][26];
	
	public static int[] pass=new int[MAXN];
	
	//每次字符串遍历结束，对应尾部位置++
	public static int[] end=new int[MAXN];
	
	//cnt用于为每个创建的节点进行编号
	public static int cnt;
	
	public static void build() {
		cnt=1;
	}
	
	//插入字符串word
	public static void insert(String word) {
		int cur=1;
		pass[cur]++;
		for(int i=0;i<word.length();i++) {
			int path=word.charAt(i)-'a';
			if(tree[cur][path]==0) {
				tree[cur][path]=++cnt;
			}
			cur=tree[cur][path];
			pass[cur]++;
		}
		end[cur]++;
	}
	
	//返回字符串word出现的次数
	public static int search(String word) {
		int cur=1;
		for(int i=0;i<word.length();i++) {
			int path=word.charAt(i)-'a';
			if(tree[cur][path]==0) {
				return 0;
			}
			cur=tree[cur][path];
		}
		return end[cur];
	}
	
	//返回以pre作为前缀的字符串个数
	public static int prefixNumber(String pre) {
		int cur=1;
		for(int i=0;i<pre.length();i++) {
			int path=pre.charAt(i)-'a';
			if(tree[cur][path]==0) {
				return 0;
			}
			cur=tree[cur][path];
		}
		return pass[cur];
	}
	
	//删除word字符串
	public static void delete(String word) {
		if(search(word)>0) {
			int cur=1;
			for(int i=0;i<word.length();i++) {
				int path=word.charAt(i)-'a';
				if(--pass[tree[cur][path]]==0) {
					tree[cur][path]=0;
					return ;
				}
				cur=tree[cur][path];
			}
			end[cur]--;
		}
	}
}
